package ds.tree;

public class SubTreeCheck {

	private boolean isIdentical(TreeNode T, TreeNode S){
		if(T == null && S == null){
			return true;
		}
		
		if(T == null || S ==null){
			return false;
		}
		
		if(T.value == S.value && 
			isIdentical(T.left, S.left)&&
			isIdentical(T.right,S.right)){
			return true;
		}
		return false;
	}
	
	public boolean isSubTree(TreeNode T , TreeNode S){
		if(S == null){
			return true;
		}
		
		if(T == null){
			return false;
		}
		if(isIdentical(T, S)){
			return true;
		}
		return isSubTree(T.left, S) || isSubTree(T.right,S);
	}
	private static class TreeNode{
		int value;
		TreeNode left = null;
		TreeNode right = null;
		
		TreeNode(int val){
			this.value = val;
		}
		
		public String toString(){
			return String.valueOf(value);
		}
	}
	private static TreeNode tree(){
		TreeNode A = new TreeNode(1);
		TreeNode B = new TreeNode(2);
		TreeNode C = new TreeNode(3);
		TreeNode D = new TreeNode(4);
		TreeNode E = new TreeNode(5);
		TreeNode F = new TreeNode(6);
		TreeNode G = new TreeNode(7);
		
		A.left = B;
		A.right = C;
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;
		
		return A;
	}
	
	private static TreeNode subTree(){
		TreeNode A = new TreeNode(3);
		TreeNode B = new TreeNode(6);
		TreeNode C = new TreeNode(7);
		A.left = B;
		A.right = C;
		
		return A;
	}
	public static void main(String[] args) {
		SubTreeCheck subTreeChk = new SubTreeCheck();
		System.out.println(subTreeChk.isSubTree(tree(), subTree()));
	}

}
